#define MAX_LEN 1024

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}


class PriorityQueue{
 public:
 PriorityQueue():currentSize(0){}
  bool insert(int data);
  bool deleteMin(int &data);

 private:
  int parent(int i){return (i-1)/2;};
  int left(int i){return 2*i+1;};
  void percolatedown(int hole);
  void percolateup(int data);
              
  int currentSize;
  int heap[MAX_LEN];
};


bool PriorityQueue::insert(int data){
  if(currentSize >= MAX_LEN)
    return false;
     
  percolateup(data);
  return true;
}

void PriorityQueue::percolateup(int data){
  int hole = currentSize++;
  int par;
  for(;hole>0; hole=par){
    par = parent(hole);
    if(heap[par] > data)
        heap[hole] = heap[par];
    else
      break;
  }
  heap[hole]=data;
}

bool PriorityQueue::deleteMin(int &data){
  if(currentSize == 0)
    return false;
  data = heap[0];
  heap[0] = heap[--currentSize];
  percolatedown(0);
  return true;
}

void PriorityQueue::percolatedown(int hole){
  int tmp = heap[hole];
  int child;

  for(;left(hole) <= currentSize; hole=child){
    child = left(hole);
    if(child != currentSize-1 && heap[child] > heap[child+1])
      child++;
    if(heap[child] < tmp)
      heap[hole]=heap[child];
    else
      break;
  }
  heap[hole] = tmp;
}
